home *** CD-ROM | disk | FTP | other *** search
/ Die Ultimative Software-P…i Collection 1996 & 1997 / Die Ultimative Software-Pakete CD-ROM fur Atari Collection 1996 & 1997.iso / g / gnu_c / gpplib22.zoo / libsrc / xbitstri.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-30  |  46.0 KB  |  2,082 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitString class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <xbitstri.h>
  26. #include <std.h>
  27. #include <limits.h>
  28. #include <xobstack.h>
  29. #include <xallocri.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32. #include <strstream.h>
  33.  
  34. void BitString::error(const char* msg) const
  35. {
  36.   (*lib_error_handler)("BitString", msg);
  37. }
  38.  
  39. //  globals
  40.  
  41. BitStrRep    _nilBitStrRep = {  0, 1, {0} };
  42.  
  43. BitString _nil_BitString;
  44.  
  45. #define MINBitStrRep_SIZE  8
  46. #define MAXBitStrRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  47.  
  48. #ifndef MALLOC_MIN_OVERHEAD
  49. #define MALLOC_MIN_OVERHEAD    4
  50. #endif
  51.  
  52. #define ONES  ((unsigned short)(~0L))
  53. #define MAXBIT  (1 << (BITSTRBITS - 1))
  54.  
  55. /*
  56.  *  bit manipulation utilities
  57. */
  58.  
  59. // break things up into .s indices and positions
  60.  
  61. inline static int BitStr_len(int l)
  62. {
  63.   return (unsigned)(l) / BITSTRBITS + 1;
  64. }
  65.  
  66.  
  67. // mask out low bits
  68.  
  69. static inline unsigned short lmask(int p)
  70. {
  71.   if (p <= 0)
  72.     return ONES;
  73.   else
  74.     return ONES << p;
  75. }
  76.  
  77. // mask out high bits
  78.  
  79. static inline unsigned short rmask(int p)
  80. {
  81.   int s = BITSTRBITS - 1 - p;
  82.   if (s <= 0)
  83.     return ONES;
  84.   else
  85.     return ONES >> s;
  86. }
  87.  
  88.  
  89. // mask out unused bits in last word of rep
  90.  
  91. inline static void check_last(BitStrRep* r)
  92. {
  93.   r->s[r->len / BITSTRBITS] &= ONES >> (BITSTRBITS - (r->len & (BITSTRBITS - 1)));
  94. }
  95.  
  96. // merge bits from next word
  97.  
  98. static inline unsigned short borrow_hi(const unsigned short a[], int ind, 
  99.                                       int maxind, int p)
  100. {
  101.   if (ind < maxind)
  102.     return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
  103.   else
  104.     return (a[ind] >> p);
  105. }
  106.  
  107. // merge bits from prev word
  108.  
  109. static inline unsigned short borrow_lo(const unsigned short a[], int ind, 
  110.                                       int minind, int p)
  111. {
  112.   if (ind > minind)
  113.     return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
  114.   else
  115.     return (a[ind] << (BITSTRBITS - 1 - p));
  116. }
  117.  
  118. // same with bounds check (for masks shorter than patterns)
  119.  
  120. static inline unsigned short safe_borrow_hi(const unsigned short a[], int ind, 
  121.                                            int maxind, int p)
  122. {
  123.   if (ind > maxind)
  124.     return 0;
  125.   else if (ind == maxind)
  126.     return(a[ind] >> p);
  127.   else
  128.     return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
  129. }
  130.  
  131.  
  132. static inline unsigned short safe_borrow_lo(const unsigned short a[], int ind, 
  133.                                             int minind, int p)
  134. {
  135.   if (ind < minind)
  136.     return 0;
  137.   else if (ind == minind)
  138.     return (a[ind] << (BITSTRBITS - 1 - p));
  139.   else
  140.     return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
  141. }
  142.  
  143. // copy bits from a word boundary
  144.  
  145. static inline void bit_copy(const unsigned short* ss, unsigned short* ds, 
  146.                             int nbits)
  147. {
  148.   if (ss != ds)
  149.   {
  150.     int n = (unsigned)(nbits) / BITSTRBITS;
  151.     if (n > 0) memmove((void*)ds, (const void*)ss, n * sizeof(short));
  152.     unsigned short m = ONES << (nbits & (BITSTRBITS - 1));
  153.     ds[n] = (ss[n] & ~m) | (ds[n] & m);
  154.   }
  155. }
  156.  
  157. // clear bits from a word boundary
  158.  
  159. static inline void bit_clear(unsigned short* ds, int nbits)
  160. {
  161.   int n = (unsigned)(nbits) / BITSTRBITS;
  162.   if (n > 0) memset((void*)ds, 0, n * sizeof(short));
  163.   ds[n] &= ONES << (nbits & (BITSTRBITS - 1));
  164. }
  165.  
  166.   
  167.  
  168. // Copy ss from starts to fences-1 into ds starting at startd.
  169. // This will work even if ss & ds overlap.
  170. // The g++ optimizer does very good things with the messy shift expressions!
  171.  
  172. static void bit_transfer(const unsigned short* ss, int starts, int fences,
  173.                          unsigned short* ds, int startd)
  174. {
  175.   if (starts >= fences || ss == 0 || (ss == ds && starts == startd))
  176.     return;
  177.  
  178.   int sind = BitStr_index(starts);
  179.   int spos = BitStr_pos(starts);
  180.   int dind = BitStr_index(startd);
  181.   int dpos = BitStr_pos(startd);
  182.  
  183.   if (spos == 0 && dpos == 0)
  184.   {
  185.     bit_copy(&ss[sind], &ds[dind], fences - starts);
  186.     return;
  187.   }
  188.  
  189.   int ends = fences - 1;
  190.   int endsind = BitStr_index(ends);
  191.   int endspos = BitStr_pos(ends);
  192.   int endd = startd + (ends - starts);
  193.   int enddind = BitStr_index(endd);
  194.   int enddpos = BitStr_pos(endd);
  195.  
  196.   if (dind == enddind)
  197.   {
  198.     if (sind == endsind)
  199.       ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | 
  200.                               (ONES << (enddpos + 1)))) | 
  201.                                 (((ss[sind] >> spos) << dpos) & 
  202.                                  ~((ONES >> (BITSTRBITS - dpos)) | 
  203.                                    (ONES << (enddpos + 1))));
  204.     else
  205.       ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | 
  206.                               (ONES << (enddpos + 1)))) | 
  207.                                 ((((ss[sind] >> spos) | 
  208.                                    (ss[sind+1] << (BITSTRBITS - spos))) 
  209.                                   << dpos) & 
  210.                                  ~((ONES >> (BITSTRBITS - dpos)) | 
  211.                                    (ONES << (enddpos + 1))));
  212.     return;
  213.   }
  214.   else if (sind == endsind)
  215.   {
  216.     unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  217.         (((ss[sind] << (BITSTRBITS - 1 - endspos)) >> 
  218.           (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  219.     ds[dind] = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
  220.         (((ss[sind] >> spos) << dpos) & ~(ONES >> (BITSTRBITS - dpos)));
  221.     ds[enddind] = saveend;
  222.     return;
  223.   }
  224.  
  225.   unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  226.     ((((ss[endsind] << (BITSTRBITS - 1 - endspos)) |
  227.        (ss[endsind-1] >> (endspos + 1))) >> 
  228.       (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  229.   unsigned short savestart = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
  230.     ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos) 
  231.      & ~(ONES >> (BITSTRBITS - dpos)));
  232.  
  233.  
  234.   if (ds != ss || startd < starts)
  235.   {
  236.     int pos = spos - dpos;
  237.     if (pos < 0)
  238.       pos += BITSTRBITS;
  239.     else
  240.       ++sind;
  241.     
  242.     for (;;)                    // lag by one in case of overlaps
  243.     {
  244.       if (dind == enddind - 1)
  245.       {
  246.         ds[dind] = savestart;
  247.         ds[enddind] = saveend;
  248.         return;
  249.       }
  250.       else
  251.       {
  252.         unsigned short tmp = ss[sind] >> pos;
  253.         if (++sind <= endsind) tmp |= ss[sind] << (BITSTRBITS - pos);
  254.         ds[dind++] = savestart;
  255.         savestart = tmp;
  256.       }
  257.     }
  258.   }
  259.   else
  260.   {
  261.     int pos = endspos - enddpos;
  262.     if (pos <= 0)
  263.     {
  264.       pos += BITSTRBITS;
  265.       --endsind;
  266.     }
  267.     for (;;)
  268.     {
  269.       if (enddind == dind + 1)
  270.       {
  271.         ds[enddind] = saveend;
  272.         ds[dind] = savestart;
  273.         return;
  274.       }
  275.       else
  276.       {
  277.         unsigned short tmp = ss[endsind] << (BITSTRBITS - pos);
  278.         if (--endsind >= sind) tmp |= ss[endsind] >> pos;
  279.         ds[enddind--] = saveend;
  280.         saveend = tmp;
  281.       }
  282.     }
  283.   }
  284. }
  285.   
  286. // allocate a new rep; pad to near a power of two
  287.  
  288. inline static BitStrRep* BSnew(int newlen)
  289. {
  290.   size_t siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(short) 
  291.     + MALLOC_MIN_OVERHEAD;
  292.   size_t allocsiz = MINBitStrRep_SIZE;;
  293.   while (allocsiz < siz) allocsiz <<= 1;
  294.   allocsiz -= MALLOC_MIN_OVERHEAD;
  295.   if (allocsiz >= MAXBitStrRep_SIZE * sizeof(short))
  296.     (*lib_error_handler)("BitString", "Requested length out of range");
  297.     
  298.   BitStrRep* rep = (BitStrRep *) new char[allocsiz];
  299.   memset(rep, 0, allocsiz);
  300.   rep->sz = (allocsiz - sizeof(BitStrRep) + sizeof(short)) / sizeof(short);
  301.   return rep;
  302. }
  303.  
  304. BitStrRep* BStr_alloc(BitStrRep* old, const unsigned short* src,
  305.                       int startpos, int endp, int newlen)
  306. {
  307.   if (old == &_nilBitStrRep) old = 0; 
  308.   if (newlen < 0) newlen = 0;
  309.   int news = BitStr_len(newlen);
  310.   BitStrRep* rep;
  311.   if (old == 0 || news > old->sz)
  312.     rep = BSnew(newlen);
  313.   else
  314.     rep = old;
  315.   rep->len = newlen;
  316.  
  317.   if (src != 0 && endp > 0 && (src != rep->s || startpos > 0)) 
  318.     bit_transfer(src, startpos, endp, rep->s, 0);
  319.  
  320.   check_last(rep);
  321.  
  322.   if (old != rep && old != 0) delete old;
  323.  
  324.   return rep;
  325. }
  326.  
  327. BitStrRep* BStr_resize(BitStrRep* old, int newlen)
  328. {
  329.   BitStrRep* rep;
  330.   if (newlen < 0) newlen = 0;
  331.   int news = BitStr_len(newlen);
  332.   if (old == 0 || old == &_nilBitStrRep)
  333.   {
  334.     rep = BSnew(newlen);
  335.   }
  336.   else if (news > old->sz)
  337.   {
  338.     rep = BSnew(newlen);
  339.     memcpy(rep->s, old->s, BitStr_len(old->len) * sizeof(short));
  340.     delete old;
  341.   }
  342.   else
  343.     rep = old;
  344.  
  345.   rep->len = newlen;
  346.   check_last(rep);
  347.   return rep;
  348. }
  349.  
  350. BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src)
  351. {
  352.   BitStrRep* rep;
  353.   if (old == src && old != &_nilBitStrRep) return old; 
  354.   if (old == &_nilBitStrRep) old = 0;
  355.   if (src == &_nilBitStrRep) src = 0;
  356.   if (src == 0)
  357.   {
  358.     if (old == 0)
  359.       rep = BSnew(0);
  360.     else
  361.       rep = old;
  362.     rep->len = 0;
  363.   }
  364.   else 
  365.   {
  366.     int newlen = src->len;
  367.     int news = BitStr_len(newlen);
  368.     if (old == 0 || news  > old->sz)
  369.     {
  370.       rep = BSnew(newlen);
  371.       if (old != 0) delete old;
  372.     }
  373.     else
  374.       rep = old;
  375.     
  376.     memcpy(rep->s, src->s, news * sizeof(short));
  377.     rep->len = newlen;
  378.   }
  379.   check_last(rep);
  380.   return rep;
  381. }
  382.  
  383.  
  384. int operator == (const BitString& x, const BitString& y)
  385. {
  386.   return x.rep->len == y.rep->len && 
  387.     memcmp((void*)x.rep->s, (void*)y.rep->s, 
  388.          BitStr_len(x.rep->len) * sizeof(short)) == 0;
  389. }
  390.  
  391. int operator <= (const BitString& x, const BitString& y)
  392. {
  393.   unsigned int  xl = x.rep->len;
  394.   unsigned int  yl = y.rep->len;
  395.   if (xl > yl)
  396.     return 0;
  397.  
  398.   const unsigned short* xs = x.rep->s;
  399.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  400.   const unsigned short* ys = y.rep->s;
  401.  
  402.   while (xs < topx)
  403.   {
  404.     unsigned short a = *xs++;
  405.     unsigned short b = *ys++;
  406.     if ((a | b) != b)
  407.       return 0;
  408.   }
  409.   return 1;
  410. }
  411.  
  412. int operator < (const BitString& x, const BitString& y)
  413. {
  414.   unsigned short xl = x.rep->len;
  415.   unsigned short yl = y.rep->len;
  416.   if (xl > yl)
  417.     return 0;
  418.  
  419.   const unsigned short* xs = x.rep->s;
  420.   const unsigned short* ys = y.rep->s;
  421.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  422.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  423.   int one_diff = 0;
  424.   while (xs < topx)
  425.   {
  426.     unsigned short a = *xs++;
  427.     unsigned short b = *ys++;
  428.     unsigned short c = a | b;
  429.     if (c != b)
  430.       return 0;
  431.     else if (c != a)
  432.       one_diff = 1;
  433.   }
  434.   if (one_diff)
  435.     return 1;
  436.   else
  437.   {
  438.     while (ys < topy)
  439.       if (*ys++ != 0)
  440.         return 1;
  441.     return 0;
  442.   }
  443. }
  444.  
  445. int lcompare(const BitString& x, const BitString& y)
  446. {
  447.   unsigned int  xl = x.rep->len;
  448.   unsigned int  yl = y.rep->len;
  449.  
  450.   const unsigned short* xs = x.rep->s;
  451.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  452.   const unsigned short* ys = y.rep->s;
  453.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  454.  
  455.   while (xs < topx && ys < topy)
  456.   {
  457.     unsigned short a = *xs++;
  458.     unsigned short b = *ys++;
  459.     if (a != b)
  460.     {
  461.       unsigned short mask = 1;
  462.       for (;;)
  463.       {
  464.         unsigned short abit = (a & mask) != 0;
  465.         unsigned short bbit = (b & mask) != 0;
  466.         int diff = abit - bbit;
  467.         if (diff != 0)
  468.           return diff;
  469.         else
  470.           mask <<= 1;
  471.       }
  472.     }
  473.   }
  474.   return xl - yl;
  475. }
  476.  
  477. int BitString::count(unsigned int b) const
  478. {
  479.   check_last(rep);
  480.   int xwds = BitStr_len(rep->len);
  481.   int xlast = BitStr_pos(rep->len);
  482.   int l = 0;
  483.   const unsigned short* s = rep->s;
  484.   const unsigned short* tops = &(s[xwds - 1]);
  485.   unsigned short a;
  486.   int i;
  487.   if (b != 0)
  488.   {
  489.     while (s < tops)
  490.     {
  491.       a = *s++;
  492.       for (i = 0; i < BITSTRBITS && a != 0; ++i)
  493.       {
  494.         if (a & 1)
  495.           ++l;
  496.         a >>= 1;
  497.       }
  498.     }
  499.     a = *s;
  500.     for (i = 0; i < xlast && a != 0; ++i)
  501.     {
  502.       if (a & 1)
  503.         ++l;
  504.       a >>= 1;
  505.     }
  506.   }
  507.   else
  508.   {
  509.     unsigned short maxbit = 1 << (BITSTRBITS - 1);
  510.     while (s < tops)
  511.     {
  512.       a = *s++;
  513.       for (i = 0; i < BITSTRBITS; ++i)
  514.       {
  515.         if ((a & maxbit) == 0)
  516.           ++l;
  517.         a <<= 1;
  518.       }
  519.     }
  520.     maxbit = 1 << (xlast - 1);
  521.     a = *s;
  522.     for (i = 0; i < xlast; ++i)
  523.     {
  524.       if ((a & maxbit) == 0)
  525.         ++l;
  526.       a <<= 1;
  527.     }
  528.   }
  529.   return l;
  530. }
  531.  
  532.  
  533. BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r)
  534. {
  535.   r = BStr_copy(r, src);
  536.   unsigned short* rs = r->s;
  537.   unsigned short* topr = &(rs[BitStr_len(r->len)]);
  538.   while (rs < topr)
  539.   {
  540.     unsigned short cmp = ~(*rs);
  541.     *rs++ = cmp;
  542.   }
  543.   check_last(r);
  544.   return r;
  545. }
  546.  
  547.  
  548. BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  549. {
  550.   int xrsame = x == r;
  551.   int yrsame = y == r;
  552.  
  553.   unsigned int  xl = x->len;
  554.   unsigned int  yl = y->len;
  555.   unsigned int  rl = (xl <= yl)? xl : yl;
  556.  
  557.   r = BStr_resize(r, rl);
  558.  
  559.   unsigned short* rs = r->s;
  560.   unsigned short* topr = &(rs[BitStr_len(rl)]);
  561.   const unsigned short* xs = (xrsame)? rs : x->s;
  562.   const unsigned short* ys = (yrsame)? rs : y->s;
  563.  
  564.   while (rs < topr) *rs++ = *xs++ & *ys++;
  565.   check_last(r);
  566.   return r;
  567. }
  568.  
  569. BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  570. {
  571.   unsigned int  xl = x->len;
  572.   unsigned int  yl = y->len;
  573.   unsigned int  rl = (xl >= yl)? xl : yl;
  574.   int xrsame = x == r;
  575.   int yrsame = y == r;
  576.  
  577.   r = BStr_resize(r, rl);
  578.  
  579.   unsigned short* rs = r->s;
  580.   const unsigned short* xs = (xrsame)? rs : x->s;
  581.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  582.   const unsigned short* ys = (yrsame)? rs : y->s;
  583.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  584.  
  585.   if (xl <= yl)
  586.   {
  587.     while (xs < topx) *rs++ = *xs++ | *ys++;
  588.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  589.   }
  590.   else
  591.   {
  592.     while (ys < topy) *rs++ = *xs++ | *ys++;
  593.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  594.   }
  595.   check_last(r);
  596.   return r;
  597. }
  598.  
  599.  
  600. BitStrRep* xor(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  601. {
  602.   unsigned int  xl = x->len;
  603.   unsigned int  yl = y->len;
  604.   unsigned int  rl = (xl >= yl)? xl : yl;
  605.   int xrsame = x == r;
  606.   int yrsame = y == r;
  607.  
  608.   r = BStr_resize(r, rl);
  609.  
  610.   unsigned short* rs = r->s;
  611.   const unsigned short* xs = (xrsame)? rs : x->s;
  612.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  613.   const unsigned short* ys = (yrsame)? rs : y->s;
  614.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  615.  
  616.   if (xl <= yl)
  617.   {
  618.     while (xs < topx) *rs++ = *xs++ ^ *ys++;
  619.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  620.   }
  621.   else
  622.   {
  623.     while (ys < topy) *rs++ = *xs++ ^ *ys++;
  624.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  625.   }
  626.   check_last(r);
  627.   return r;
  628. }
  629.  
  630.  
  631. BitStrRep* diff(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  632. {
  633.   unsigned int  xl = x->len;
  634.   unsigned int  yl = y->len;
  635.   int xrsame = x == y;
  636.   int yrsame = y == r;
  637.  
  638.   r = BStr_resize(r, xl);
  639.  
  640.   unsigned short* rs = r->s;
  641.   const unsigned short* xs = (xrsame)? rs : x->s;
  642.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  643.   const unsigned short* ys = (yrsame)? rs : y->s;
  644.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  645.  
  646.   if (xl <= yl)
  647.   {
  648.     while (xs < topx) *rs++ = *xs++ & ~(*ys++);
  649.   }
  650.   else
  651.   {
  652.     while (ys < topy) *rs++ = *xs++ & ~(*ys++);
  653.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  654.   }
  655.   check_last(r);
  656.   return r;
  657. }
  658.  
  659.  
  660. BitStrRep* cat(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  661. {
  662.   unsigned int  xl = x->len;
  663.   unsigned int  yl = y->len;
  664.   unsigned int  rl = xl + yl;
  665.   int xrsame = x == r;
  666.   int yrsame = y == r;
  667.  
  668.   if (yrsame)
  669.   {
  670.     if (xrsame)
  671.     {
  672.       r = BStr_resize(r, rl);
  673.       bit_transfer(r->s, 0, yl, r->s, xl);
  674.     }
  675.     else
  676.     {
  677.       BitStrRep* tmp = BStr_copy(0, y);
  678.       r = BStr_resize(r, rl);
  679.       bit_copy(x->s, r->s, xl);
  680.       bit_transfer(tmp->s, 0, yl, r->s, xl);
  681.       delete tmp;
  682.     }
  683.   }
  684.   else
  685.   {
  686.     r = BStr_resize(r, rl);
  687.     if (!xrsame) bit_copy(x->s, r->s, xl);
  688.     bit_transfer(y->s, 0, yl, r->s, xl);
  689.   }
  690.   check_last(r);
  691.   return r;
  692. }
  693.  
  694. BitStrRep* cat(const BitStrRep* x, unsigned int bit, BitStrRep* r)
  695. {
  696.   unsigned int  xl = x->len;
  697.   int xrsame = x == r;
  698.   r = BStr_resize(r, xl+1);
  699.   if (!xrsame) bit_copy(x->s, r->s, xl);
  700.   if (bit)
  701.     r->s[BitStr_index(xl)] |= (1 << (BitStr_pos(xl)));
  702.   else
  703.     r->s[BitStr_index(xl)] &= ~(1 << (BitStr_pos(xl)));
  704.   check_last(r);
  705.   return r;
  706. }
  707.  
  708. BitStrRep* lshift(const BitStrRep* x, int s, BitStrRep* r)
  709. {
  710.   int xrsame = x == r;
  711.   int  xl = x->len;
  712.   int  rl = xl + s;
  713.   if (s == 0)
  714.     r = BStr_copy(r, x);
  715.   else if (rl <= 0)
  716.   {
  717.     r = BStr_resize(r, 0);
  718.     r->len = 0;
  719.     r->s[0] = 0;
  720.   }
  721.   else if (s > 0)
  722.   {
  723.     r = BStr_resize(r, rl);
  724.     const unsigned short* xs = (xrsame)? r->s : x->s;
  725.     bit_transfer(xs, 0, xl, r->s, s);
  726.     bit_clear(r->s, s);
  727.   }
  728.   else if (xrsame)
  729.   {
  730.     r = BStr_resize(r, xl);
  731.     r->len = rl;
  732.     bit_transfer(r->s, -s, xl, r->s, 0);
  733.   }
  734.   else
  735.   {
  736.     r = BStr_resize(r, rl);
  737.     bit_transfer(x->s, -s, xl, r->s, 0);
  738.   }
  739.   check_last(r);
  740.   return r;
  741. }
  742.  
  743.  
  744. void BitString::set(int p)
  745. {
  746.   if (p < 0) error("Illegal bit index");
  747.   if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  748.   rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
  749. }
  750.  
  751. void BitString::assign(int p, unsigned int bit)
  752. {
  753.   if (p < 0) error("Illegal bit index");
  754.   if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  755.   if (bit)
  756.     rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
  757.   else
  758.     rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
  759. }
  760.  
  761. void BitString::clear(int p)
  762. {
  763.   if (p < 0) error("Illegal bit index");
  764.   if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  765.   rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
  766. }
  767.  
  768. void BitString::clear()
  769. {
  770.   if (rep == &_nilBitStrRep) return;
  771.   bit_clear(rep->s, rep->len);
  772. }
  773.  
  774. void BitString::set()
  775. {
  776.   if (rep == &_nilBitStrRep) return;
  777.   unsigned short* s = rep->s;
  778.   unsigned short* tops = &(s[BitStr_len(rep->len)]);
  779.   while (s < tops) *s++ = ONES;
  780.   check_last(rep);
  781. }
  782.  
  783. void BitString::invert(int p)
  784. {
  785.   if (p < 0) error("Illegal bit index");
  786.   if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  787.   rep->s[BitStr_index(p)] ^= (1 << (BitStr_pos(p)));
  788. }
  789.  
  790.  
  791.  
  792. void BitString::set(int from, int to)
  793. {
  794.   if (from < 0 || from > to) error("Illegal bit index");
  795.   if ((size_t)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  796.  
  797.   int ind1 = BitStr_index(from);
  798.   int pos1 = BitStr_pos(from);
  799.   int ind2 = BitStr_index(to);
  800.   int pos2 = BitStr_pos(to);
  801.   unsigned short* s = &(rep->s[ind1]);
  802.   unsigned short m1 = lmask(pos1);
  803.   unsigned short m2 = rmask(pos2);
  804.   if (ind2 == ind1)
  805.     *s |= m1 & m2;
  806.   else
  807.   {
  808.     *s++ |= m1;
  809.     unsigned short* top = &(rep->s[ind2]);
  810.     *top |= m2;
  811.     while (s < top)
  812.       *s++ = ONES;
  813.   }
  814. }
  815.  
  816. void BitString::clear(int from, int to)
  817. {
  818.   if (from < 0 || from > to) error("Illegal bit index");
  819.   if ((size_t)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  820.  
  821.   int ind1 = BitStr_index(from);
  822.   int pos1 = BitStr_pos(from);
  823.   int ind2 = BitStr_index(to);
  824.   int pos2 = BitStr_pos(to);
  825.   unsigned short* s = &(rep->s[ind1]);
  826.   unsigned short m1 = lmask(pos1);
  827.   unsigned short m2 = rmask(pos2);
  828.   if (ind2 == ind1)
  829.     *s &= ~(m1 & m2);
  830.   else
  831.   {
  832.     *s++ &= ~m1;
  833.     unsigned short* top = &(rep->s[ind2]);
  834.     *top &= ~m2;
  835.     while (s < top)
  836.       *s++ = 0;
  837.   }
  838. }
  839.  
  840. void BitString::invert(int from, int to)
  841. {
  842.   if (from < 0 || from > to) error("Illegal bit index");
  843.   if ((size_t)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  844.  
  845.   int ind1 = BitStr_index(from);
  846.   int pos1 = BitStr_pos(from);
  847.   int ind2 = BitStr_index(to);
  848.   int pos2 = BitStr_pos(to);
  849.   unsigned short* s = &(rep->s[ind1]);
  850.   unsigned short m1 = lmask(pos1);
  851.   unsigned short m2 = rmask(pos2);
  852.   if (ind2 == ind1)
  853.     *s ^= m1 & m2;
  854.   else
  855.   {
  856.     *s++ ^= m1;
  857.     unsigned short* top = &(rep->s[ind2]);
  858.     *top ^= m2;
  859.     while (s < top)
  860.     {
  861.       unsigned short cmp = ~(*s);
  862.       *s++ = cmp;
  863.     }
  864.   }
  865. }
  866.  
  867.  
  868. int BitString::test(int from, int to) const
  869. {
  870.   if (from < 0 || from > to || (size_t)(from) >= rep->len) return 0;
  871.   
  872.   int ind1 = BitStr_index(from);
  873.   int pos1 = BitStr_pos(from);
  874.   int ind2 = BitStr_index(to);
  875.   int pos2 = BitStr_pos(to);
  876.   
  877.   if ((size_t)(to) >= rep->len)
  878.   {
  879.     ind2 = BitStr_index(rep->len - 1);
  880.     pos2 = BitStr_pos(rep->len - 1);
  881.   }
  882.   
  883.   const unsigned short* s = &(rep->s[ind1]);
  884.   unsigned short m1 = lmask(pos1);
  885.   unsigned short m2 = rmask(pos2);
  886.   
  887.   if (ind2 == ind1)
  888.     return (*s & m1 & m2) != 0;
  889.   else
  890.   {
  891.     if (*s++ & m1)
  892.       return 1;
  893.     unsigned short* top = &(rep->s[ind2]);
  894.     if (*top & m2)
  895.       return 1;
  896.     while (s < top)
  897.       if (*s++ != 0) 
  898.         return 1;
  899.     return 0;
  900.   }
  901. }
  902.  
  903. int BitString::next(int p, unsigned int b) const
  904. {
  905.   if ((size_t)(++p) >= rep->len)
  906.     return -1;
  907.  
  908.   int ind = BitStr_index(p);
  909.   int pos = BitStr_pos(p);
  910.   int l = BitStr_len(rep->len);
  911.  
  912.   int j = ind;
  913.   const unsigned short* s = rep->s;
  914.   unsigned short a = s[j] >> pos;
  915.   int i = pos;
  916.  
  917.   if (b != 0)
  918.   {
  919.     for (; i < BITSTRBITS && a != 0; ++i)
  920.     {
  921.       if (a & 1)
  922.         return j * BITSTRBITS + i;
  923.       a >>= 1;
  924.     }
  925.     for (++j; j < l; ++j)
  926.     {
  927.       a = s[j];
  928.       for (i = 0; i < BITSTRBITS && a != 0; ++i)
  929.       {
  930.         if (a & 1)
  931.           return j * BITSTRBITS + i;
  932.         a >>= 1;
  933.       }
  934.     }
  935.     return -1;
  936.   }
  937.   else
  938.   {
  939.     int last = BitStr_pos(rep->len);
  940.     if (j == l - 1)
  941.     {
  942.       for (; i < last; ++i)
  943.       {
  944.         if ((a & 1) == 0)
  945.           return j * BITSTRBITS + i;
  946.         a >>= 1;
  947.       }
  948.       return -1;
  949.     }
  950.  
  951.     for (; i < BITSTRBITS; ++i)
  952.     {
  953.       if ((a & 1) == 0)
  954.         return j * BITSTRBITS + i;
  955.       a >>= 1;
  956.     }
  957.     for (++j; j < l - 1; ++j)
  958.     {
  959.       a = s[j];
  960.       if (a != ONES)
  961.       {
  962.         for (i = 0; i < BITSTRBITS; ++i)
  963.         {
  964.           if ((a & 1) == 0)
  965.             return j * BITSTRBITS + i;
  966.           a >>= 1;
  967.         }
  968.       }
  969.     }
  970.     a = s[j];
  971.     for (i = 0; i < last; ++i)
  972.     {
  973.       if ((a & 1) == 0)
  974.         return j * BITSTRBITS + i;
  975.       a >>= 1;
  976.     }
  977.     return -1;
  978.   }
  979. }
  980.  
  981. int BitString::prev(int p, unsigned int b) const
  982. {
  983.   if (--p < 0)
  984.     return -1;
  985.  
  986.   int ind = BitStr_index(p);
  987.   int pos = BitStr_pos(p);
  988.  
  989.   const unsigned short* s = rep->s;
  990.  
  991.   if ((size_t)(p) >= rep->len)
  992.   {
  993.     ind = BitStr_index(rep->len - 1);
  994.     pos = BitStr_pos(rep->len - 1);
  995.   }
  996.  
  997.   int j = ind;
  998.   unsigned short a = s[j];
  999.  
  1000.   int i = pos;
  1001.   unsigned short maxbit = 1 << pos;
  1002.  
  1003.   if (b != 0)
  1004.   {
  1005.     for (; i >= 0 && a != 0; --i)
  1006.     {
  1007.       if (a & maxbit)
  1008.         return j * BITSTRBITS + i;
  1009.       a <<= 1;
  1010.     }
  1011.     maxbit = 1 << (BITSTRBITS - 1);
  1012.     for (--j; j >= 0; --j)
  1013.     {
  1014.       a = s[j];
  1015.       for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i)
  1016.       {
  1017.         if (a & maxbit)
  1018.           return j * BITSTRBITS + i;
  1019.         a <<= 1;
  1020.       }
  1021.     }
  1022.     return -1;
  1023.   }
  1024.   else
  1025.   {
  1026.     if (a != ONES)
  1027.     {
  1028.       for (; i >= 0; --i)
  1029.       {
  1030.         if ((a & maxbit) == 0)
  1031.           return j * BITSTRBITS + i;
  1032.         a <<= 1;
  1033.       }
  1034.     }
  1035.     maxbit = 1 << (BITSTRBITS - 1);
  1036.     for (--j; j >= 0; --j)
  1037.     {
  1038.       a = s[j];
  1039.       if (a != ONES)
  1040.       {
  1041.         for (i = BITSTRBITS - 1; i >= 0; --i)
  1042.         {
  1043.           if ((a & maxbit) == 0)
  1044.             return j * BITSTRBITS + i;
  1045.           a <<= 1;
  1046.         }
  1047.       }
  1048.     }
  1049.     return -1;
  1050.   }
  1051. }
  1052.  
  1053.  
  1054. int BitString::search(int startx, int lengthx, 
  1055.                       const unsigned short* ys, int starty, int lengthy) const
  1056. {
  1057.   const unsigned short* xs = rep->s;
  1058.   int ylen = lengthy - starty;
  1059.   int righty = lengthy - 1;
  1060.   int rev = startx < 0;
  1061.   if (rev)
  1062.   {
  1063.     int leftx = 0;
  1064.     int rightx = lengthx + startx;
  1065.     startx = rightx - ylen + 1;
  1066.     if (ylen == 0) return startx;
  1067.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  1068.     
  1069.     int xind = BitStr_index(startx);
  1070.     int xpos = BitStr_pos(startx);
  1071.     int yind = BitStr_index(starty);
  1072.     int ypos = BitStr_pos(starty);
  1073.     
  1074.     int rightxind = BitStr_index(rightx);
  1075.  
  1076.     unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
  1077.   
  1078.     int rightyind = BitStr_index(righty);
  1079.     int rightypos = BitStr_pos(righty);
  1080.     unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
  1081.     unsigned short ymask;
  1082.     if (yind == rightyind)
  1083.       ymask = rmask(rightypos);
  1084.     else if (yind+1 == rightyind)
  1085.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  1086.     else
  1087.       ymask = ONES;
  1088.     
  1089.     int p = startx;
  1090.     for (;;)
  1091.     {
  1092.       if ((x & ymask) == y)
  1093.       {
  1094.         int xi = xind;
  1095.         int yi = yind;
  1096.         for (;;)
  1097.         {
  1098.           if (++yi > rightyind || ++xi > rightxind)
  1099.             return p;
  1100.           unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
  1101.           unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
  1102.           if (yi == rightyind)
  1103.             tx &= rmask(rightypos);
  1104.           else if (yi+1 == rightyind)
  1105.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1106.           if (tx != ty)
  1107.             break;
  1108.         }
  1109.       }
  1110.       if (--p < leftx)
  1111.         return -1;
  1112.       if (--xpos < 0)
  1113.       {
  1114.         xpos = BITSTRBITS - 1;
  1115.         --xind;
  1116.       }
  1117.       x = borrow_hi(xs, xind, rightxind, xpos);
  1118.     }
  1119.   }
  1120.   else
  1121.   {
  1122.  
  1123.     int rightx = lengthx - 1;
  1124.     if (ylen == 0) return startx;
  1125.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  1126.     
  1127.     int xind = BitStr_index(startx);
  1128.     int xpos = BitStr_pos(startx);
  1129.     int yind = BitStr_index(starty);
  1130.     int ypos = BitStr_pos(starty);
  1131.  
  1132.     int rightxind = BitStr_index(rightx);
  1133.  
  1134.     unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
  1135.     unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1136.   
  1137.     int rightyind = BitStr_index(righty);
  1138.     int rightypos = BitStr_pos(righty);
  1139.     unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
  1140.     unsigned short ymask;
  1141.     if (yind == rightyind)
  1142.       ymask = rmask(rightypos);
  1143.     else if (yind+1 == rightyind)
  1144.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  1145.     else
  1146.       ymask = ONES;
  1147.   
  1148.     int p = startx;
  1149.     for (;;)
  1150.     {
  1151.       if ((x & ymask) == y)
  1152.       {
  1153.         int xi = xind;
  1154.         int yi = yind;
  1155.         for (;;)
  1156.         {
  1157.           if (++yi > rightyind || ++xi > rightxind)
  1158.             return p;
  1159.           unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
  1160.           unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
  1161.           if (yi == rightyind)
  1162.             tx &= rmask(rightypos);
  1163.           else if (yi+1 == rightyind)
  1164.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1165.           if (tx != ty)
  1166.             break;
  1167.         }
  1168.       }
  1169.       if (++p > rightx)
  1170.         return -1;
  1171.       if (++xpos == BITSTRBITS)
  1172.       {
  1173.         xpos = 0;
  1174.         x = xs[++xind];
  1175.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1176.       }
  1177.       else
  1178.       {
  1179.         x >>= 1;
  1180.         if (nextx & 1)
  1181.           x |= MAXBIT;
  1182.         nextx >>= 1;
  1183.       }
  1184.     }
  1185.   }
  1186. }
  1187.  
  1188.  
  1189. int BitPattern::search(const unsigned short* xs, int startx, int lengthx) const
  1190. {
  1191.   const unsigned short* ys = pattern.rep->s;
  1192.   const unsigned short* ms = mask.rep->s;
  1193.   int righty = pattern.rep->len - 1;
  1194.   int rightm = mask.rep->len - 1;
  1195.  
  1196.   int rev = startx < 0;
  1197.   if (rev)
  1198.   {
  1199.     int leftx = 0;
  1200.     int rightx = lengthx + startx;
  1201.     startx = rightx - righty;
  1202.  
  1203.     if (righty < 0) return startx;
  1204.     if (startx < 0 || startx >= lengthx) return -1;
  1205.   
  1206.     int xind = BitStr_index(startx);
  1207.     int xpos = BitStr_pos(startx);
  1208.     
  1209.     int rightxind = BitStr_index(rightx);
  1210.  
  1211.     int rightmind = BitStr_index(rightm);
  1212.     int rightyind = BitStr_index(righty);
  1213.     
  1214.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1215.     unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
  1216.     unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  1217.     
  1218.     int p = startx;
  1219.     for (;;)
  1220.     {
  1221.       if ((x & m) == y)
  1222.       {
  1223.         int xi = xind;
  1224.         int yi = 0;
  1225.         for (;;)
  1226.         {
  1227.           if (++yi > rightyind || ++xi > rightxind)
  1228.             return p;
  1229.           unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
  1230.           unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
  1231.           unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  1232.           if ((tx & tm) != (ty & tm))
  1233.             break;
  1234.         }
  1235.       }
  1236.       if (--p < leftx)
  1237.         return -1;
  1238.       if (--xpos < 0)
  1239.       {
  1240.         xpos = BITSTRBITS - 1;
  1241.         --xind;
  1242.       }
  1243.       x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1244.     }
  1245.   }
  1246.   else
  1247.   {
  1248.  
  1249.     int rightx = lengthx - 1;
  1250.  
  1251.     if (righty < 0) return startx;
  1252.     if (startx < 0 || startx >= lengthx) return -1;
  1253.     
  1254.     int xind = BitStr_index(startx);
  1255.     int xpos = BitStr_pos(startx);
  1256.     
  1257.     int rightxind = BitStr_index(rightx);
  1258.  
  1259.     int rightmind = BitStr_index(rightm);
  1260.     int rightyind = BitStr_index(righty);
  1261.     
  1262.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1263.     unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
  1264.     unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  1265.  
  1266.     unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1267.     
  1268.     int p = startx;
  1269.     for (;;)
  1270.     {
  1271.       if ((x & m) == y)
  1272.       {
  1273.         int xi = xind;
  1274.         int yi = 0;
  1275.         for (;;)
  1276.         {
  1277.           if (++yi > rightyind || ++xi > rightxind)
  1278.             return p;
  1279.           unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
  1280.           unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
  1281.           unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  1282.           if ((tx & tm) != (ty & tm))
  1283.             break;
  1284.         }
  1285.       }
  1286.       if (++p > rightx)
  1287.         return -1;
  1288.       if (++xpos == BITSTRBITS)
  1289.       {
  1290.         xpos = 0;
  1291.         x = xs[++xind];
  1292.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1293.       }
  1294.       else
  1295.       {
  1296.         x >>= 1;
  1297.         if (nextx & 1)
  1298.           x |= MAXBIT;
  1299.         nextx >>= 1;
  1300.       }
  1301.     }
  1302.   }
  1303. }
  1304.  
  1305. int BitString::match(int startx, int lengthx, int exact, 
  1306.                      const unsigned short* ys, int starty, int yl) const
  1307. {
  1308.   const unsigned short* xs = rep->s;
  1309.   int ylen = yl - starty;
  1310.   int righty = yl - 1;
  1311.  
  1312.   int rightx;
  1313.   int rev = startx < 0;
  1314.   if (rev)
  1315.   {
  1316.     rightx = lengthx + startx;
  1317.     startx = rightx - ylen + 1;
  1318.     if (exact && startx != 0)
  1319.       return 0;
  1320.   }
  1321.   else
  1322.   {
  1323.     rightx = lengthx - 1;
  1324.     if (exact && rightx - startx != righty)
  1325.       return 0;
  1326.   }
  1327.  
  1328.   if (ylen == 0) return 1;
  1329.   if (righty < 0 || startx < 0 || startx >= lengthx) return 0;
  1330.   
  1331.   int xi   = BitStr_index(startx);
  1332.   int xpos = BitStr_pos(startx);
  1333.   int yi   = BitStr_index(starty);
  1334.   int ypos = BitStr_pos(starty);
  1335.  
  1336.   int rightxind = BitStr_index(rightx);
  1337.   int rightyind = BitStr_index(righty);
  1338.   int rightypos = BitStr_pos(righty);
  1339.  
  1340.   for (;;)
  1341.   {
  1342.     unsigned short x = borrow_hi(xs, xi, rightxind, xpos);
  1343.     unsigned short y = borrow_hi(ys, yi, rightyind, ypos);
  1344.     if (yi == rightyind)
  1345.       x &= rmask(rightypos);
  1346.     else if (yi+1 == rightyind)
  1347.       x &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1348.     if (x != y)
  1349.       return 0;
  1350.     else if (++yi > rightyind || ++xi > rightxind)
  1351.       return 1;
  1352.   }
  1353. }
  1354.  
  1355. int BitPattern::match(const unsigned short* xs, int startx, 
  1356.                       int lengthx, int exact) const
  1357. {
  1358.   const unsigned short* ys = pattern.rep->s;
  1359.   int righty = pattern.rep->len - 1;
  1360.   unsigned short* ms = mask.rep->s;
  1361.   int rightm = mask.rep->len - 1;
  1362.  
  1363.   int rightx;
  1364.   int rev = startx < 0;
  1365.   if (rev)
  1366.   {
  1367.     rightx = lengthx + startx;
  1368.     startx = rightx - righty;
  1369.     if (exact && startx != 0)
  1370.       return 0;
  1371.   }
  1372.   else
  1373.   {
  1374.     rightx = lengthx - 1;
  1375.     if (exact && rightx - startx != righty)
  1376.       return 0;
  1377.   }
  1378.  
  1379.   if (righty < 0) return 1;
  1380.   if (startx < 0 || startx >= lengthx) return 0;
  1381.   
  1382.   int xind = BitStr_index(startx);
  1383.   int xpos = BitStr_pos(startx);
  1384.   int yind = 0;
  1385.  
  1386.   int rightxind = BitStr_index(rightx);
  1387.   int rightyind = BitStr_index(righty);
  1388.   int rightmind = BitStr_index(rightm);
  1389.  
  1390.   for(;;)
  1391.   {
  1392.     unsigned short m = safe_borrow_hi(ms, yind, rightmind, 0);
  1393.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos) & m;
  1394.     unsigned short y = safe_borrow_hi(ys, yind, rightyind, 0) & m;
  1395.     if (x != y)
  1396.       return 0;
  1397.     else if (++yind > rightyind || ++xind > rightxind)
  1398.       return 1;
  1399.   }
  1400. }
  1401.  
  1402. void BitSubString::operator = (const BitString& y)
  1403. {
  1404.   if (&S == &_nil_BitString) return;
  1405.   BitStrRep* targ = S.rep;
  1406.  
  1407.   unsigned int ylen = y.rep->len;
  1408.   int sl = targ->len - len + ylen;
  1409.  
  1410.   if (y.rep == targ || ylen > len)
  1411.   {
  1412.     BitStrRep* oldtarg = targ;
  1413.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1414.     bit_transfer(oldtarg->s, 0, pos, targ->s, 0);
  1415.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1416.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen);
  1417.     delete oldtarg;
  1418.   }
  1419.   else if (len == ylen)
  1420.     bit_transfer(y.rep->s, 0, len, targ->s, pos);
  1421.   else if (ylen < len)
  1422.   {
  1423.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1424.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + ylen);
  1425.     targ->len = sl;
  1426.   }
  1427.   check_last(targ);
  1428.   S.rep = targ;
  1429. }
  1430.  
  1431. void BitSubString::operator = (const BitSubString& y)
  1432. {
  1433.   if (&S == &_nil_BitString) return;
  1434.   BitStrRep* targ = S.rep;
  1435.   
  1436.   if (len == 0 || pos >= targ->len)
  1437.     return;
  1438.   
  1439.   int sl = targ->len - len + y.len;
  1440.   
  1441.   if (y.S.rep == targ || y.len > len)
  1442.   {
  1443.     BitStrRep* oldtarg = targ;
  1444.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1445.     bit_copy(oldtarg->s, targ->s, pos);
  1446.     bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1447.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len);
  1448.     delete oldtarg;
  1449.   }
  1450.   else if (len == y.len)
  1451.     bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1452.   else if (y.len < len)
  1453.   {
  1454.     bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1455.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + y.len);
  1456.     targ->len = sl;
  1457.   }
  1458.   check_last(targ);
  1459.   S.rep = targ;
  1460. }
  1461.  
  1462. BitSubString BitString::at(int first, int len)
  1463. {
  1464.   return _substr(first, len);
  1465. }
  1466.  
  1467. BitSubString BitString::before(int pos)
  1468. {
  1469.   return _substr(0, pos);
  1470. }
  1471.  
  1472. BitSubString BitString::after(int pos)
  1473. {
  1474.   return _substr(pos + 1, rep->len - (pos + 1));
  1475. }
  1476.  
  1477. BitSubString BitString::at(const BitString& y, int startpos)
  1478. {
  1479.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1480.   return _substr(first,  y.rep->len);
  1481. }
  1482.  
  1483. BitSubString BitString::before(const BitString& y, int startpos)
  1484. {
  1485.   int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1486.   return _substr(0, last);
  1487. }
  1488.  
  1489. BitSubString BitString::after(const BitString& y, int startpos)
  1490. {
  1491.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1492.   if (first >= 0) first += y.rep->len;
  1493.   return _substr(first, rep->len - first);
  1494. }
  1495.  
  1496.  
  1497. BitSubString BitString::at(const BitSubString& y, int startpos)
  1498. {
  1499.   int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1500.   return _substr(first, y.len);
  1501. }
  1502.  
  1503. BitSubString BitString::before(const BitSubString& y, int startpos)
  1504. {
  1505.   int last = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1506.   return _substr(0, last);
  1507. }
  1508.  
  1509. BitSubString BitString::after(const BitSubString& y, int startpos)
  1510. {
  1511.   int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1512.   if (first >= 0) first += y.len;
  1513.   return _substr(first, rep->len - first);
  1514. }
  1515.  
  1516. BitSubString BitString::at(const BitPattern& r, int startpos)
  1517. {
  1518.   int first = r.search(rep->s, startpos, rep->len);
  1519.   return _substr(first, r.pattern.rep->len);
  1520. }
  1521.  
  1522.  
  1523. BitSubString BitString::before(const BitPattern& r, int startpos)
  1524. {
  1525.   int first = r.search(rep->s, startpos, rep->len);
  1526.   return _substr(0, first);
  1527. }
  1528.  
  1529. BitSubString BitString::after(const BitPattern& r, int startpos)
  1530. {
  1531.   int first = r.search(rep->s, startpos, rep->len);
  1532.   if (first >= 0) first += r.pattern.rep->len;
  1533.   return _substr(first, rep->len - first);
  1534. }
  1535.  
  1536. #if defined(__GNUG__) && !defined(NO_NRV)
  1537.  
  1538. BitString common_prefix(const BitString& x, const BitString& y, int startpos)
  1539.      return r
  1540. {
  1541.   unsigned int  xl = x.rep->len;
  1542.   unsigned int  yl = y.rep->len;
  1543.  
  1544.   unsigned int startx, starty;
  1545.   if (startpos < 0)
  1546.   {
  1547.     startx = xl + startpos;
  1548.     starty = yl + startpos;
  1549.   }
  1550.   else
  1551.     startx = starty = startpos;
  1552.  
  1553.   if (startx >= xl || starty >= yl)
  1554.     return;
  1555.  
  1556.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1557.   unsigned short a = *xs++;
  1558.   unsigned int xp = startx;
  1559.  
  1560.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1561.   unsigned short b = *ys++;
  1562.   unsigned int yp = starty;
  1563.  
  1564.   for(; xp < xl && yp < yl; ++xp, ++yp)
  1565.   {
  1566.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1567.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1568.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1569.       break;
  1570.     if (xbit == MAXBIT)
  1571.       a = *xs++;
  1572.     if (ybit == MAXBIT)
  1573.       b = *ys++;
  1574.   }
  1575.   r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
  1576. }
  1577.  
  1578.  
  1579. BitString common_suffix(const BitString& x, const BitString& y, int startpos)
  1580.      return r;
  1581. {
  1582.   unsigned int  xl = x.rep->len;
  1583.   unsigned int  yl = y.rep->len;
  1584.  
  1585.   unsigned int startx, starty;
  1586.   if (startpos < 0)
  1587.   {
  1588.     startx = xl + startpos;
  1589.     starty = yl + startpos;
  1590.   }
  1591.   else
  1592.     startx = starty = startpos;
  1593.  
  1594.   if (startx >= xl || starty >= yl)
  1595.     return;
  1596.  
  1597.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1598.   unsigned short a = *xs--;
  1599.   int xp = startx;
  1600.  
  1601.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1602.   unsigned short b = *ys--;
  1603.   int yp = starty;
  1604.  
  1605.   for(; xp >= 0 && yp >= 0; --xp, --yp)
  1606.   {
  1607.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1608.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1609.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1610.       break;
  1611.     if (xbit == 1)
  1612.       a = *xs--;
  1613.     if (ybit == 1)
  1614.       b = *ys--;
  1615.   }
  1616.   r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
  1617. }
  1618.  
  1619. BitString reverse(const BitString& x) return r
  1620. {
  1621.   size_t  yl = x.rep->len;
  1622.   BitStrRep* y = BStr_resize(0, yl);
  1623.   if (yl > 0)
  1624.   {
  1625.     const unsigned short* ls = x.rep->s;
  1626.     unsigned short lm = 1;
  1627.     unsigned short* rs = &(y->s[BitStr_index(yl - 1)]);
  1628.     unsigned short rm = 1 << (BitStr_pos(yl - 1));
  1629.     for (size_t  l = 0; l < yl; ++l)
  1630.     {
  1631.       if (*ls & lm)
  1632.         *rs |= rm;
  1633.       if (lm == MAXBIT)
  1634.       {
  1635.         ++ls;
  1636.         lm = 1;
  1637.       }
  1638.       else
  1639.         lm <<= 1;
  1640.       if (rm == 1)
  1641.       {
  1642.         --rs;
  1643.         rm = MAXBIT;
  1644.       }
  1645.       else
  1646.         rm >>= 1;
  1647.     }
  1648.   }
  1649.   r.rep = y;
  1650. }
  1651.  
  1652. BitString atoBitString(const char* s, char f, char t) return res
  1653. {
  1654.   int sl = strlen(s);
  1655.   BitStrRep* r = BStr_resize(0, sl);
  1656.   if (sl != 0)
  1657.   {
  1658.     unsigned int  rl = 0;
  1659.     unsigned short* rs = r->s;
  1660.     unsigned short a = 0;
  1661.     unsigned short m = 1;
  1662.     unsigned int  i = 0;
  1663.     for(;;)
  1664.     {
  1665.       char ch = s[i];
  1666.       if (ch != t && ch != f)
  1667.       {
  1668.         *rs = a;
  1669.         break;
  1670.       }
  1671.       ++rl;
  1672.       if (ch == t)
  1673.         a |= m;
  1674.       if (++i == sl)
  1675.       {
  1676.         *rs = a;
  1677.         break;
  1678.       }
  1679.       else if (i % BITSTRBITS == 0)
  1680.       {
  1681.         *rs++ = a;
  1682.         a = 0;
  1683.         m = 1;
  1684.       }
  1685.       else
  1686.         m <<= 1;
  1687.     }
  1688.     r = BStr_resize(r, rl);
  1689.   }
  1690.   res.rep = r;
  1691. }
  1692.  
  1693. BitPattern atoBitPattern(const char* s, char f,char t,char x) return r
  1694. {
  1695.   int sl = strlen(s);
  1696.   if (sl != 0)
  1697.   {
  1698.     unsigned int  rl = 0;
  1699.     r.pattern.rep = BStr_resize(r.pattern.rep, sl);
  1700.     r.mask.rep = BStr_resize(r.mask.rep, sl);
  1701.     unsigned short* rs = r.pattern.rep->s;
  1702.     unsigned short* ms = r.mask.rep->s;
  1703.     unsigned short a = 0;
  1704.     unsigned short b = 0;
  1705.     unsigned short m = 1;
  1706.     unsigned int  i = 0;
  1707.     for(;;)
  1708.     {
  1709.       char ch = s[i];
  1710.       if (ch != t && ch != f && ch != x)
  1711.       {
  1712.         *rs = a;
  1713.         *ms = b;
  1714.         break;
  1715.       }
  1716.       ++rl;
  1717.       if (ch == t)
  1718.       {
  1719.         a |= m;
  1720.         b |= m;
  1721.       }
  1722.       else if (ch == f)
  1723.       {
  1724.         b |= m;
  1725.       }
  1726.       if (++i == sl)
  1727.       {
  1728.         *rs = a;
  1729.         *ms = b;
  1730.         break;
  1731.       }
  1732.       else if (i % BITSTRBITS == 0)
  1733.       {
  1734.         *rs++ = a;
  1735.         *ms++ = b;
  1736.         a = 0;
  1737.         b = 0;
  1738.         m = 1;
  1739.       }
  1740.       else
  1741.         m <<= 1;
  1742.     }
  1743.     r.pattern.rep = BStr_resize(r.pattern.rep, rl);
  1744.     r.mask.rep = BStr_resize(r.mask.rep, rl);
  1745.   }
  1746.   return;
  1747. }
  1748.  
  1749. #else /* NO_NRV */
  1750.  
  1751. BitString common_prefix(const BitString& x, const BitString& y, int startpos)
  1752. {
  1753.   BitString r;
  1754.  
  1755.   unsigned int  xl = x.rep->len;
  1756.   unsigned int  yl = y.rep->len;
  1757.  
  1758.   int startx, starty;
  1759.   if (startpos < 0)
  1760.   {
  1761.     startx = xl + startpos;
  1762.     starty = yl + startpos;
  1763.   }
  1764.   else
  1765.     startx = starty = startpos;
  1766.  
  1767.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1768.     return r;
  1769.  
  1770.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1771.   unsigned short a = *xs++;
  1772.   int xp = startx;
  1773.  
  1774.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1775.   unsigned short b = *ys++;
  1776.   int yp = starty;
  1777.  
  1778.   for(; xp < xl && yp < yl; ++xp, ++yp)
  1779.   {
  1780.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1781.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1782.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1783.       break;
  1784.     if (xbit == MAXBIT)
  1785.       a = *xs++;
  1786.     if (ybit == MAXBIT)
  1787.       b = *ys++;
  1788.   }
  1789.   r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
  1790.   return r;
  1791. }
  1792.  
  1793.  
  1794. BitString common_suffix(const BitString& x, const BitString& y, int startpos)
  1795. {
  1796.   BitString r;
  1797.   unsigned int  xl = x.rep->len;
  1798.   unsigned int  yl = y.rep->len;
  1799.  
  1800.   int startx, starty;
  1801.   if (startpos < 0)
  1802.   {
  1803.     startx = xl + startpos;
  1804.     starty = yl + startpos;
  1805.   }
  1806.   else
  1807.     startx = starty = startpos;
  1808.  
  1809.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1810.     return r;
  1811.  
  1812.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1813.   unsigned short a = *xs--;
  1814.   int xp = startx;
  1815.  
  1816.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1817.   unsigned short b = *ys--;
  1818.   int yp = starty;
  1819.  
  1820.   for(; xp >= 0 && yp >= 0; --xp, --yp)
  1821.   {
  1822.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1823.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1824.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1825.       break;
  1826.     if (xbit == 1)
  1827.       a = *xs--;
  1828.     if (ybit == 1)
  1829.       b = *ys--;
  1830.   }
  1831.   r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
  1832.   return r;
  1833. }
  1834.  
  1835. BitString reverse(const BitString& x)
  1836. {
  1837.   BitString r;
  1838.   size_t  yl = x.rep->len;
  1839.   BitStrRep* y = BStr_resize(0, yl);
  1840.   if (yl > 0)
  1841.   {
  1842.     const unsigned short* ls = x.rep->s;
  1843.     unsigned short lm = 1;
  1844.     unsigned short* rs = &(y->s[BitStr_index(yl - 1)]);
  1845.     unsigned short rm = 1 << (BitStr_pos(yl - 1));
  1846.     for (size_t  l = 0; l < yl; ++l)
  1847.     {
  1848.       if (*ls & lm)
  1849.         *rs |= rm;
  1850.       if (lm == MAXBIT)
  1851.       {
  1852.         ++ls;
  1853.         lm = 1;
  1854.       }
  1855.       else
  1856.         lm <<= 1;
  1857.       if (rm == 1)
  1858.       {
  1859.         --rs;
  1860.         rm = MAXBIT;
  1861.       }
  1862.       else
  1863.         rm >>= 1;
  1864.     }
  1865.   }
  1866.   r.rep = y;
  1867.   return r;
  1868. }
  1869.  
  1870. BitString atoBitString(const char* s, char f, char t)
  1871. {
  1872.   BitString res;
  1873.   size_t sl = strlen(s);
  1874.   BitStrRep* r = BStr_resize(0, sl);
  1875.   if (sl != 0)
  1876.   {
  1877.     size_t  rl = 0;
  1878.     unsigned short* rs = r->s;
  1879.     unsigned short a = 0;
  1880.     unsigned short m = 1;
  1881.     size_t  i = 0;
  1882.     for(;;)
  1883.     {
  1884.       char ch = s[i];
  1885.       if (ch != t && ch != f)
  1886.       {
  1887.         *rs = a;
  1888.         break;
  1889.       }
  1890.       ++rl;
  1891.       if (ch == t)
  1892.         a |= m;
  1893.       if (++i == sl)
  1894.       {
  1895.         *rs = a;
  1896.         break;
  1897.       }
  1898.       else if (i % BITSTRBITS == 0)
  1899.       {
  1900.         *rs++ = a;
  1901.         a = 0;
  1902.         m = 1;
  1903.       }
  1904.       else
  1905.         m <<= 1;
  1906.     }
  1907.     r = BStr_resize(r, rl);
  1908.   }
  1909.   res.rep = r;
  1910.   return res;
  1911. }
  1912.  
  1913. BitPattern atoBitPattern(const char* s, char f,char t,char x)
  1914. {
  1915.   BitPattern r;
  1916.   size_t sl = strlen(s);
  1917.   if (sl != 0)
  1918.   {
  1919.     size_t  rl = 0;
  1920.     r.pattern.rep = BStr_resize(r.pattern.rep, sl);
  1921.     r.mask.rep = BStr_resize(r.mask.rep, sl);
  1922.     unsigned short* rs = r.pattern.rep->s;
  1923.     unsigned short* ms = r.mask.rep->s;
  1924.     unsigned short a = 0;
  1925.     unsigned short b = 0;
  1926.     unsigned short m = 1;
  1927.     size_t  i = 0;
  1928.     for(;;)
  1929.     {
  1930.       char ch = s[i];
  1931.       if (ch != t && ch != f && ch != x)
  1932.       {
  1933.         *rs = a;
  1934.         *ms = b;
  1935.         break;
  1936.       }
  1937.       ++rl;
  1938.       if (ch == t)
  1939.       {
  1940.         a |= m;
  1941.         b |= m;
  1942.       }
  1943.       else if (ch == f)
  1944.       {
  1945.         b |= m;
  1946.       }
  1947.       if (++i == sl)
  1948.       {
  1949.         *rs = a;
  1950.         *ms = b;
  1951.         break;
  1952.       }
  1953.       else if (i % BITSTRBITS == 0)
  1954.       {
  1955.         *rs++ = a;
  1956.         *ms++ = b;
  1957.         a = 0;
  1958.         b = 0;
  1959.         m = 1;
  1960.       }
  1961.       else
  1962.         m <<= 1;
  1963.     }
  1964.     r.pattern.rep = BStr_resize(r.pattern.rep, rl);
  1965.     r.mask.rep = BStr_resize(r.mask.rep, rl);
  1966.   }
  1967.   return r;
  1968. }
  1969.  
  1970. #endif
  1971.  
  1972. extern AllocRing _libgxx_fmtq;
  1973.  
  1974. void BitString::printon(ostream& os, char f, char t) const
  1975. {
  1976.   size_t  xl = rep->len;
  1977.   const unsigned short* ptr = rep->s;
  1978.   register streambuf *sb = os.rdbuf();
  1979.   unsigned short a = 0;
  1980.  
  1981.   for (size_t i = 0; i < xl; ++i)
  1982.   {
  1983.     if (i % BITSTRBITS == 0)
  1984.       a = *ptr++;
  1985.     sb->sputc((a & 1)? t : f);
  1986.     a >>= 1;
  1987.   }
  1988. }
  1989.  
  1990. const char* BitStringtoa(const BitString& x, char f, char t)
  1991. {
  1992.   size_t wrksiz = x.length() + 2;
  1993.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  1994.   ostrstream stream(fmtbase, wrksiz);
  1995.   
  1996.   x.printon(stream, f, t);
  1997.   stream << ends;
  1998.   return fmtbase;
  1999. }
  2000.  
  2001. ostream& operator << (ostream& s, const BitString& x)
  2002. {
  2003.   if (s.opfx())
  2004.     x.printon(s);
  2005.   return s;
  2006. }
  2007.  
  2008. const char* BitPatterntoa(const BitPattern& p, char f,char t,char x)
  2009. {
  2010.   size_t  pl = p.pattern.rep->len;
  2011.   size_t  ml = p.mask.rep->len;
  2012.   size_t  l = (pl <= ml)? pl : ml;
  2013.  
  2014.   size_t wrksiz = l + 2;
  2015.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  2016.   ostrstream stream(fmtbase, wrksiz);
  2017.   
  2018.   p.printon(stream, f, t, x);
  2019.   stream << ends;
  2020.   return fmtbase;
  2021. }
  2022.  
  2023. void BitPattern::printon(ostream& s, char f,char t,char x) const
  2024. {
  2025.   unsigned int  pl = pattern.rep->len;
  2026.   unsigned int  ml = mask.rep->len;
  2027.   unsigned int  l = (pl <= ml)? pl : ml;
  2028.   register streambuf *sb = s.rdbuf();
  2029.  
  2030.   const unsigned short* ps = pattern.rep->s;
  2031.   const unsigned short* ms = mask.rep->s;
  2032.   unsigned short a = 0;
  2033.   unsigned short m = 0;
  2034.  
  2035.   for (size_t  i = 0; i < l; ++i)
  2036.   {
  2037.     if (i % BITSTRBITS == 0)
  2038.     {
  2039.       a = *ps++;
  2040.       m = *ms++;
  2041.     }
  2042.     if (m & 1)
  2043.       sb->sputc((a & 1)? t : f);
  2044.     else
  2045.       sb->sputc(x);
  2046.     a >>= 1;
  2047.     m >>= 1;
  2048.   }
  2049. }
  2050.  
  2051. ostream& operator << (ostream& s, const BitPattern& x)
  2052. {
  2053.   if (s.opfx())
  2054.     x.printon(s);
  2055.   return s;
  2056. }
  2057.  
  2058.  
  2059. int BitString::OK() const
  2060. {
  2061.   int v = rep != 0;             // have a rep;
  2062.   v &= BitStr_len(rep->len) <= rep->sz; // within allocated size
  2063.   if (!v) error("invariant failure");
  2064.   return v;
  2065. }
  2066.  
  2067. int BitSubString::OK() const
  2068. {
  2069.   int v = S.OK();               // valid BitString
  2070.   v &= pos + len <= S.rep->len; // within bounds of targ
  2071.   if (!v) S.error("BitSubString invariant failure");
  2072.   return v;
  2073. }
  2074.  
  2075. int BitPattern::OK() const
  2076. {
  2077.   int v = pattern.OK() && mask.OK();
  2078.   if (!v) pattern.error("BitPattern invariant failure");
  2079.   return v;
  2080. }
  2081.  
  2082.